package a09_贪心算法;

/**
 * <p>
 * a23_监控二叉树复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/1/20
 */
public class a23_监控二叉树复习1 {

    //三个状态：未覆盖0 有摄像头1 已覆盖2
    //从底往上
    //左右有一个未覆盖，则根节点1
    //左右有一个有摄像头，则根节点2
    //左右都已覆盖，则根节点0

    //为了统一规则：叶子节点的下面的也搞个状态
    //如果是有摄像头，则叶子节点已覆盖
    //如果是有未覆盖，则叶子节点有摄像头
    //如果是有已覆盖，则叶子节点的父节点才有摄像头
    public int minCameraCover(TreeNode root) {
        int traversal = traversal(root);
        if (traversal == 0) {
            result++;
        }
        return result;
    }

    private int result;

    private int traversal(TreeNode node){
        if (node == null) {
            return 2;
        }

        int leftStatus = traversal(node.left);
        int rightStatus = traversal(node.right);
        if(leftStatus == 2 && rightStatus == 2){
            return 0;
        }
        if(leftStatus == 0 || rightStatus == 0){
            result++;
            return 1;
        }

        if(leftStatus == 1 || rightStatus == 1){
            return 2;
        }
        return -1;
    }
}
